// https://www.lintcode.com/problem/backpack-ii

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        int[] ret = new int[m + 1];
        Arrays.fill(ret, 0);
        for (int i = 0; i < A.length; ++i) {
            for (int j = m; j >= 0; --j) {
                if (j >= A[i]) {
                    ret[j] = Math.max(ret[j], ret[j - A[i]] + V[i]);
                }
            }
        }
        return ret[m];
    }
}